package code.BinaryTree.在二叉树中增加一行;

import struct.Tree;
import struct.TreeNode;

public class Solution {

	public static void main(String[] args) {
		Solution solution = new Solution();
		TreeNode tree = Tree.constructTree("[4,2,6,3,1,5]");
		TreeNode node = solution.addOneRow(tree, 1, 3);
		System.out.println(node);
	}

	public TreeNode addOneRow(TreeNode root, int v, int d) {
		TreeNode pre = new TreeNode(0);//1.创建一个父亲节点
		pre.left = root;//2.将当前的根节点作为该父亲节点的左子树。
		addOneRowHelper(pre, 0, v, d);//4.在二叉树中增加一行，需要记录当前的层级
		return pre.left;//3.反正这个虚拟节点的左子树，也就是修改后的root节点
	}

	private void addOneRowHelper(TreeNode cur, int level, int v, int d) {
		if (cur == null) {//5.递归终止条件，在空节点无需操作。
			return;
		}
		if (level + 1 == d) {//8.在 d-1 层的时候就可以拼接子树了。
			TreeNode left = cur.left;//9.记录该结点的左子树
			TreeNode right = cur.right;//10.记录该结点的右子树
			cur.left = new TreeNode(v);//11.替换当前结点的左孩子为新的v节点
			cur.right = new TreeNode(v);//12.替换当前结点的右孩子为新的v节点
			cur.left.left = left;//13.将原左子树作为左孩子的左子树
			cur.right.right = right;//14.将原右子树作为右孩子的右子树
			return;//15.操作完这个节点可以直接返回了，没有必要在遍历下一层的节点。
		}
		addOneRowHelper(cur.left, level + 1, v, d);//6.递归操作左子树，记录下一层所在层数
		addOneRowHelper(cur.right, level + 1, v, d);//7.递归操作左子树，记录下一层所在层数
	}
}
